package org.example.myleet.rosalind.cunr;

/**
 * 关于Unrooted binary tree的解释
 * https://en.wikipedia.org/wiki/Unrooted_binary_tree
 * An unrooted binary tree is an unrooted tree in which each vertex has either one or three neighbors
 * 所有的节点要么是1度要么是3度，最少有2个节点（每个节点都是子节点）
 * 关于Enumeration章节
 * An unrooted binary tree on n labeled leaves can be formed by connecting the nth leaf to a new node in the middle of any of the edges of an unrooted binary tree on n − 1 labeled leaves. There are 2n − 5 edges at which the nth node can be attached; therefore, the number of trees on n leaves is larger than the number of trees on n − 1 leaves by a factor of 2n − 5. Thus, the number of trees on n labeled leaves is the double factorial.
 * (2n - 5)!! = (2n - 5) * (2n - 7) * ...... * (2-even or 1-odd)
 * 关于双阶乘的定义
 * https://baike.baidu.com/item/%E5%8F%8C%E9%98%B6%E4%B9%98/9500461?fr=aladdin
 */
public class Solution {

    private static final int MODULO = 1000000;

    public static void main(String[] args) {
//        int n = 5;
//        int n = 6;
//        int n = 11;
        int n = 993;
        int a = 2 * n - 5;
        int res = a;
        while (a > 2) {
            res *= (a = a - 2);
            res %= MODULO;
        }
        System.out.println(res);
    }
}
